/*
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void ToBSTHelper(TreeNode **node, ListNode *head) {
        if (!head) return;
        else if (!head->next) {
            *node = new TreeNode(head->val); 
            return;
        }
        ListNode *l1, *l2;
        l1 = l2 = head;
        // l1 points to mid point after loop
        while (l2->next && l2->next->next && l2->next->next->next) {
            l2 = l2->next;
            l2 = l2->next;
            l1 = l1->next;
        }
        *node = new TreeNode(l1->next->val);
        // right tree
        ToBSTHelper(&((*node)->right), l1->next->next);
        l1->next = NULL;    // splice the list
        // left tree
        ToBSTHelper(&((*node)->left), head);
    }
    TreeNode *sortedListToBST(ListNode *head) {
        TreeNode *root = NULL;
        ToBSTHelper(&root, head);
        return root;
    }
};
